package interview.loop;

import java.util.ArrayList;
import java.util.Arrays;

import interview.common.Node;
import interview.recursion.LinkedListCreator;

public class LinkedListReverser
{
	public Node reverserLinkedList(Node head)
	{
		// 定义循环不变式中所用到的2个变量
		Node newHead = null;
		Node curHead = head;

		// Loop invariant:规定循环不变式：
		// newHead points to the linked list already reversed.
		// curHead points to the linked list not yet reversed.
		// 进入循环之前：满足【循环不变式】

		// Loop invariant holds.
		while (curHead != null)// 退出循环的条件
		{
			// curHead == null【先决条件】——>循环体能够运行的唯一条件curHead != null

			// 考虑中间状态：循环已经做了很多轮，下一轮怎么做(不要考虑第一轮怎么做)

			// Loop invariant holds.
			// 找到结点5，记录它
			Node next = curHead.getNext();

			// 把curHead的next指向newHead
			curHead.setNext(newHead);// 4——>3

			// newHead和curHead往右移
			newHead = curHead;// 3——>4
			curHead = next;// 4——>5
			// Loop invariant holds.
		}

		// Loop invariant holds.
		return newHead;// newHead就是我们想要的结果
	}

	public static void main(String[] args)
	{
		LinkedListCreator creator = new LinkedListCreator();
		LinkedListReverser reverser = new LinkedListReverser();

		// 建一个空传
		Node.printLinkedList(reverser.reverserLinkedList(creator.creatLinkedList(new ArrayList<>())));
		// 建一个只有一个节点的传
		Node.printLinkedList(reverser.reverserLinkedList(creator.creatLinkedList(Arrays.asList(1))));
		// 建一个普通的
		Node.printLinkedList(reverser.reverserLinkedList(creator.creatLinkedList(Arrays.asList(1, 2, 3, 4, 5))));
		// 打印linked list，见Node.java
	}

}
